package com.it.zhangjun.arithmetic.队列.单调队列;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

/**
 * @author zhangj
 * @description 滑动窗口最大值
 * @date 2021-03-26 14:16
 */
public class LT_滑动窗口最大值 {
    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3};
        int[] slidingWindow = maxSlidingWindow(nums, 3);
        for (int e : slidingWindow) {
            System.out.println(e);
        }
    }

    /**
     * 单调队列使用双端队列来实现
     */
    private static ArrayDeque<Integer> Q = new ArrayDeque<>();

    /**
     * 入队的时候，last方向入队，但是入队的时候需要保证整个队列的数值是单调的
     *
     * @param value
     */
    private static void push(int value) {
        while (!Q.isEmpty() && Q.getLast() < value) {
            Q.removeLast();
        }
        Q.addLast(value);
    }

    /**
     * 出队的时候，要相等的时候才会出队
     *
     * @param value
     */
    public static void pop(int value) {
        if (!Q.isEmpty() && Q.getFirst() == value) {
            Q.removeFirst();
        }
    }

    public static int[] maxSlidingWindow(int[] nums, int k) {
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            push(nums[i]);
            //如果队列中的元素还少于K个，这个时候还不能去取最大值
            if (i < k - 1) {
                continue;
            }
            //队首元素就是最大值
            ans.add(Q.getFirst());
            //移除队首元素
            pop(nums[i - k + 1]);
        }
        // 将ans转换成为数组返回!
        return ans.stream().mapToInt(Integer::valueOf).toArray();
    }
}